﻿//描述
//你有一个背包，最多能容纳的体积是V。
//现在有n个物品，第i个物品的体积为vi, 价值为wi。
//（1）求这个背包至多能装多大价值的物品？
//（2）若背包恰好装满，求至多能装多大价值的物品？
//
//输入描述：
//第一行两个整数n和V，表示物品个数和背包体积。
//接下来n行，每行两个数vi​和wi，表示第i个物品的体积和价值。
//1≤n, V, vi, wi≤1000
//
//输出描述：
//输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
//
//输入：
//	3 5
//	2 10
//	4 5
//	1 4
//输出：
//	14
//	9
//说明：
//	装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
//
//输入：
//	3 8
//	12 6
//	11 8
//	6 8
//输出：
//	8
//	0
//说明：
//装第三个物品时总价值最大但是不满，装满背包无解。
//备注：
//要求O(nV)的时间复杂度，O(V)空间复杂度

#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main() {
    //读⼊数据

    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    //解决第⼀问

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) //修改遍历顺序

        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }

    cout << dp[n][V] << endl;
    //解决第⼆问

    memset(dp, 0, sizeof dp);
    for (int j = 1; j <= V; j++) dp[0][j] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) //修改遍历顺序

        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i] && dp[i - 1][j - v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }

    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}